/*
给定一个二叉树，判断它是否是高度平衡的二叉树。
 */

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isBalanced = function (root) {
  const resultData = process(root)
  return resultData.isBalanced
}

class ReturnData {
  constructor (isBalanced, height) {
    this.isBalanced = isBalanced
    this.height = height
  }
}

/**
 * 判断当前以当前节点为root的树是否平衡, 返回值:{isBalance, height}
 * @param node
 * @return {ReturnData}
 */
function process (node) {
  if (!node) {
    // node为null
    return new ReturnData(true, 0)
  }
  const leftData = process(node.left)
  if (!leftData.isBalanced) {
    // 左树不平衡
    return new ReturnData(false, 0)
  }
  const rightData = process(node.right)
  if (!rightData.isBalanced) {
    // 右树不平衡
    return new ReturnData(false, 0)
  }
  if (Math.abs(leftData.height - rightData.height) > 1) {
    // 高度差超过1
    return new ReturnData(false, 0)
  }

  return new ReturnData(true, Math.max(leftData.height, rightData.height) + 1)
}
